package com.cfwx.datastructure.sort;

/**
   算法基本思路：归并排序采用分治法的基本思想
    　设两个有序的子文件(相当于输入堆)放在同一向量中相邻的位置上：R[low..m]，R[m+1..high]，
         先将它们合并到一个局部的暂存向量R1(相当于输出堆)中，待合并完成后将R1复制回R[low..high]中。

（1）合并过程
    　        合并过程中，设置i，j和p三个指针，其初值分别指向这三个记录区的起始位置。
        合并时依次比较R[i]和R[j]的关键字，取关键字较小的记录复制到R1[p]中， 然后
        将被复制记录的指针i或j加1，以及指向复制位置的指针p加1。
       重复这一过程直至两个输入的子文件有一个已全部复制完毕(不妨称其为空)，此时将
       另一非空的子文件中剩余记录依次复制到R1中即可。

（2）动态申请R1
    　实现时，R1是动态申请的，因为申请的空间可能很大，故须加入申请空间是否成功的处理。

 二路归并实现：
   设归并排序的当前区间是R[low..high]，分治法的三个步骤是：
   ①分解：将当前区间一分为二，即求分裂点min=[(low+high)/2]取整                
   ②求解：递归地对两个子区间R[low..mid]和R[mid+1..high]进行归并排序；
   ③组合：将已排序的两个子区间R[low..mid]和R[mid+1..high]归并为一个有序的区间R[low..high]。
   递归的终结条件：子区间长度为1（一个记录自然有序）。

 *
 */
public class MergeSort {

	//分治
	public void mergeSort(int[] R,int low ,int high){
		int mid;
		if(low<high){//区间长度大于1
			mid=(low+high)/2; //分解
			mergeSort(R,low,mid); //递归地对R[low..mid]排序
			mergeSort(R,mid+1,high); //递归地对R[mid+1..high]排序
			merge(R,low,mid,high); //组合，将两个有序区归并为一个有序区
		}	
	}

	//归并
	void merge(int[] R,int low,int m,int high)
	{//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的子文件R[low..high]
		int i=low,j=m+1,p=0; //置初始值
		int[] R1 = new int[high-low+1];
		while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上
			R1[p++]=(R[i]<=R[j])?R[i++]:R[j++];
		while(i<=m) //若第1个子文件非空，则复制剩余记录到R1中
			R1[p++]=R[i++];
		while(j<=high) //若第2个子文件非空，则复制剩余记录到R1中
			R1[p++]=R[j++];
		for(p=0,i=low;i<=high;p++,i++)
			R[i]=R1[p];//归并完成后将结果复制回R[low..high]
	} 


	public static void main(String[] args){
		int num[] = new int[] {0,2221, 5, 40, 32, 2,7,111,9,4};
		new MergeSort().mergeSort(num,1,num.length-1);
		for (int x = 0; x < num.length-1; x++) {
			System.out.print(num[x+1] + " ");
		}


	}

}
/**
 * 
算法分析

1、稳定性
     　归并排序是一种稳定的排序。

2、存储结构要求
    　可用顺序存储结构。也易于在链表上实现。

3、时间复杂度
    　对长度为n的文件，需进行[lgn]趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlgn)。

4、空间复杂度
   　 需要一个辅助向量来暂存两有序子文件归并的结果，故其辅助空间复杂度为O(n)，显然它不是就地排序。
 */
